class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        for (int start = 0; start < gcd(n,k); start++){
            int current = start;
            int prev = nums[current], tmp;
            do {
                // 计算下一个待交换的元素位置
                int next = (current+k)%n;
                // 将待交换的元素值和prev互换
                tmp = nums[next];
                nums[next] = prev;
                prev = tmp;
                // 更新当前位置
                current = next;
            }while(current!=start);
        }
    }

    private static int gcd(int a, int b) {
        return b > 0 ? gcd(b, a%b) : a;
    }

    public void rotate_3r(int[] nums, int k) {
        int n = nums.length;
        k %= n;

        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);

    }

    private static void reverse(int[] nums, int i, int j){
        int tmp;
        while (i < j){
            tmp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = tmp;
        }
    }
}